【算法导论】链表队列

​ 链表队列很简单，之前看到过，没有用程序实现。其原理就是遵循FIFO原则,只能从队首取元素，从队尾插入元素，就和排队模型一样。因此只需要队首指针和队尾指针就可以方便的进行队列操作。因为在最近看的图论算法中，经常用到队列，在这里就先用程序实现链表队列。

​ 和单链表一样，为了运算方便，我们也在队头节点前附加一个头结点，且头指针指向头结点。其链表队列的示意图如下：

下面是具体的程序实现：

#include<stdio.h>
#include<stdlib.h>


typedef struct node//定义节点的结构体
{
	int data;
	struct node *next;
}linklist;

typedef struct//定义链表
{
	linklist *front,*rear;//定义指向节点的头尾指针
}linkqueue;

void SetNull(linkqueue *q)//置空队列（含空的头节点，便于处理）
{
	q->front=(linklist *)malloc(sizeof(linklist));
	q->front->next=NULL;
	q->rear=q->front;
}

int Empty(linkqueue *q)//判断队列是否为空
{
	if(q->front==q->rear)
		return 1;
	else 
		return 0;
}

int Front(linkqueue *q)//取出队列的头元素
{
	if(Empty(q))
	{
		printf("queue is empty!");
		return -1;
	}
	else
		return q->front->next->data;//注意有头指针，该指针的下个元素才是第一个元素
}

void ENqueue(linkqueue *q,int x)//进队列
{
	linklist * newnode=(linklist *)malloc(sizeof(linklist));
    q->rear->next=newnode;
	q->rear=newnode;
	q->rear->data=x;
	q->rear->next=NULL;
	
}

int DEqueue(linkqueue *q)//出队列
{
	int temp;
	linklist *s;
	if(Empty(q))
	{
		printf("queue is empty!");
		return -1;
	}
	else
	{
		s=q->front->next;
		if(s->next==NULL)
		{
			q->front->next=NULL;
			q->rear=q->front;
		}
		else
			q->front->next=s->next;
		temp=s->data;
		return temp;
	}
}


void main()
{
	linkqueue q;//这里是产生队列q,而不是产生指向队列的指正，是为了方便初始化。
	            //如果为指针的话，必须初始化，则头尾指针无法初始化。
	
	SetNull(&q);//相当于初始化
	ENqueue(&q,2);//将关键字2入队
	ENqueue(&q,3);//将关键字3入队
	ENqueue(&q,4);//将关键字4入队
	DEqueue(&q);//将关键字2出队
	DEqueue(&q);//将关键字3出队
	int a=0;
    a=Front(&q);//取队头元素

	printf("%d\n",a);
}